package dynProg.solvers;

import dynProg.ArrayHelper;
import dynProg.Solver;

/**
 * 
 * @author Stephan Veenstra
 * @version 1.0
 */

public class TopDownSolver implements Solver {

	Boolean[][] matrix;  // Ik gebruik Boolean(object) ipv boolean(primitive) zodat de standaardwaarde null(niet eerder berekend) kan zijn

	@Override
	public boolean solve(int[] numbers, int sum) {
		matrix = new Boolean[numbers.length][sum+1];
        boolean a = findAnswer(numbers, sum);
        return a;
	}
	
	private boolean findAnswer(int[] numbers, int sum)
	{
		if( sum == 0 ) return true;			// Je kunt altijd 0 maken door niets op te tellen
        if( numbers.length == 0 ) return false; // Zonder getalen is er geen som anders dan 0
        
        if(matrix[numbers.length -1][sum] == null)
        	matrix[numbers.length -1][sum] = doSolve(numbers, sum);
        
        return matrix[numbers.length -1][sum];
	}

	private boolean doSolve(int[] numbers, int sum)
	{
        int n = numbers.length - 1;	// Bepaal de lengte van het subprobleem
        int[] subProblem = new int[n]; // Maak het sub probleem array
        for(int i = 0; i < n; i++){ // vul het subProbleem
            subProblem[i] = numbers[i];
        }

        if(findAnswer(subProblem, sum) || findAnswer(subProblem, sum - numbers[n])) // Roep de methode nog twee keer aan voor het subprobleem
        	return true;												// 1 keer voor sum en een keer voor sum - laatste getal van numbers
        else 
        	return false;
	}
	
}
